package pro.softzhang.algo.lc500;

/**
 *
 */
public class LC540_SingleElementInASortedArray {
    public static void main(String[] args) {
        int[] nums = {1,1,2,3,3,4,4,8,8};
        int single = new Solution().singleNonDuplicate(nums);
        System.out.println(single);
    }

    static class Solution {
        public int singleNonDuplicate(int[] nums) {
            int left = 0, right = nums.length / 2;
            while (left <= right) {
                int middle = (left + right) / 2;
                int i = middle * 2;
                if(i < nums.length - 1 && nums[i] != nums[i + 1]) {
                    if(middle == 0 || nums[i - 2] == nums[i - 1]) {
                        return nums[i];
                    }
                    right = middle - 1;
                } else {
                    left = middle + 1;
                }
            }
            return nums[nums.length - 1];
        }
    }
}